GATE CSE 2004
Q1.
The microinstructions stored in the control memory of a processor have a width of 26 bits. Each microinstruction is divided into three fields: a micro-operation field of 13 bits, a next address field (X), and a MUX select field (Y). There are 8 status bits in the inputs of the MUX. How many bits are there in the X and Y fields, and what is the size of the control memory in number of words?Q2.
Which of the following Addressing Modess are suitable for program relocation at run time? (i) Absolute addressing (ii) Based addressing (iii) Relative addressing (iv) Indirect addressingQ3.
Consider the following C program segment: char p[20]; char *s = "string"; int length = strlen(s); int i; for (i = 0; i < length; i++) p[i] = s[length - i]; printf("%s",p); The output of the program isQ4.
Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1 x M2 will beQ5.
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?Q6.
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program isQ7.
The Asymptotic Notation of the following C function is (assume n \gt 0) int recursive (int n) { if (n == 1) return (1); else return (recursive (n - 1) + recursive (n - 1)); }Q8.
Let A[1,..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose Asymptotic Notation is \theta(m). Consider the following program fragment written in a C like language: counter = 0; for (i = 1; i < = n; i++) { if (A[i] == 1) counter++; else { f(counter); counter = 0; } } The complexity of this program fragment isQ9.
Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that he colour pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?Q10.
Level order traversal of a rooted tree can be done by starting from the root and performing